package org.example.linkList;

import org.example.model.ListNode;

import java.util.ArrayList;
import java.util.Stack;

/**
 * 从尾到头打印链表
 * @author: guochao.bj@fang.com
 * @createDate: 2022/5/13 15:23
 */
public class practiceLinkList01 {


    /**
     * 逆序打印链表
     *  1->2->3
     *  打印321
     * 方法1：使用栈
     * 方法2：递归
     * 方法3：双指针逆序链表
     */


    /**
     * 递归遍历链表，先添加后置数据
     * 然后添加自身
     * @author guochao.bj@fang.com
     * @date 2022/5/13
     */
    public static ArrayList<String> printListFromTailToHead1(ListNode listNode){
        ArrayList<String> listNodes = new ArrayList<>();

        if (listNode!=null){
            //先添加后置节点
            listNodes.addAll(printListFromTailToHead1(listNode.getNext()));
            //添加本身
            listNodes.add(listNode.getValue());
        }

        return listNodes;
    }


    /**
     * 使用栈
     * 首先逆序首先想到栈处理。
     * @date 2022/5/13
     */
    public static ArrayList<String> printListFromTailToHead2(ListNode listNode){
        ArrayList<String> listNodes = new ArrayList<>();
        Stack<String> stackList = new Stack<>();
        if (listNode!=null){
            stackList.add(listNode.getValue());
            listNode=listNode.getNext();
        }

        while (!stackList.isEmpty()){
            listNodes.add(stackList.pop());
        }
        return listNodes;
    }


    /**
     * 双指针逆序
     */
    public static ArrayList<String> printListFromTailToHead3(ListNode listNode){
        ArrayList<String> listNodes = new ArrayList<>();
        if (listNode!=null){
            //只有一个节点
            if (listNode.getNext()==null){
                listNodes.add(listNode.getValue());
                return listNodes;
            }else {

                ListNode p1=listNode;
                ListNode p2=null;
                //双指针逆序
                while (p1!=null){
                    ListNode temp=p1.getNext();
                    p1.setNext(p2);
                    p2=p1;
                    p1=temp;
                }
                ListNode next = p2.getNext();
                if (next!=null){
                    listNodes.add(p2.getValue());
                    p2=p2.getNext();
                }
            }
        }
        return listNodes;
    }


}
